// 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序

// 思路，双指针法，平方后的打破有序的元素只能在两端，所以指向两端比较是否平方后小值会超过右端的大值
// 时间复杂度：O(n)
// 空间复杂度：O(1)

function sortedSquares(arr) {
    let left = 0
    let right = arr.length - 1
    let index = arr.length - 1
    let ans = []
    while (left <= right) {
        let leftSquareVal = Math.pow(arr[left], 2)
        let rightSquareVal = Math.pow(arr[right], 2)
        if (leftSquareVal > rightSquareVal) {
            ans[index] = leftSquareVal
            left++
        } else {
            ans[index] = rightSquareVal
            right--
        }
        index--
    }
    return ans
}

console.log(sortedSquares([-5, 1, 2, 3, 6]))